// 堆:本质上就是一颗完全二叉树
// 1、大顶堆

// 根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大顶堆。大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。

// 2、小顶堆

// 根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者，称为小顶堆。小根堆要求根节点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值。


// 堆的构建:大顶堆:从第一个非叶子节点开始一次对数组中的元素进行下沉操作
// 和孩子节点的最大值max比较
// 大于max ---不需要在下沉
// 小于max ---和max交换位置 继续和下一层孩子节点比较 直到队列末尾
function ajustMaxHeap (array, index, length) {
    for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
        if (i + 1 < length && array[i + 1] > array[i]) {
            i++
        }
        if (array[index] >= [array[i]]) {
            break
        } else {
            [array[index], array[i]] = [array[i], array[index]]
            index = i
        }
    }
}
function createMaxHeap (arr, length) {
    for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        ajustMaxHeap(arr, i, length)
    }
    return arr
}
/**
 * 小顶堆:从第一个非叶子节点开始一次对数组中的元素进行下沉操作
 *    和孩子节点的最小值min比较
 *     小于min 不需要在下沉
 *     大于min和min交换位置 继续和下一层孩子节点比较 支队队列末尾
 */
function ajustMinHeap (array, index, length) {
    // 2*index+1 获取左节点
    for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
        if (i + 1 < length && array[i + 1], array[i]) {
            i++
        }
        if (array[index] < [array[i]]) {
            break
        } else {
            [array[index], array[i]] = [array[i], array[index]]
            index = i
        }
    }
}
function createMinHeap (arr, length) {
    for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        ajustMinHeap(arr, i, length)
    }
    return arr
}